package org.kfive.nova.algorithm.binarytree;

import org.apache.log4j.Logger;

/**
 * Created by admin on 2016-07-31.
 * AVL树
 */
public class BalanceBinaryTree {

    /* the log */
    private Logger LOG = Logger.getLogger(BalanceBinaryTree.class);

    /* 树根 */
    private TreeNode root;

    /* constructor */
    public BalanceBinaryTree(){
        this.root = null;
    }

    /**
     * 中序遍历
     * @param node
     * @return
     */
    public String inOrder(TreeNode node){
        StringBuffer sb = new StringBuffer();
        sb.append(inOrder(node.getLeftTree()));
        if(node!=null){
            sb.append(node.getValue());
        }
        sb.append(inOrder(node.getRightTree()));
        return sb.toString();
    }
    /**
     * 平衡树添加节点
     * @param value
     * @return
     */
    public void insert(TreeNode node,int value){
        //空树
        if(node==null){
            node = new TreeNode();
            node.setLeftTree(null);
            node.setRightTree(null);
            node.setHeight(getHeight(node));
            node.setValue(value);
        }else if(node.getValue()>value) {
            insert(node.getLeftTree(),value);
            if(getHeight(node.getLeftTree())-getHeight(node.getRightTree())==2){
                if(value<node.getLeftTree().getValue()){
                    simpleRightRotate(node);
                }else {
                    leftRightRotate(node);
                }
            }
        }else if(node.getValue()<value){
            insert(node.getRightTree(),value);
            if(getHeight(node.getRightTree())-getHeight(node.getLeftTree())==2){
                if(value<node.getRightTree().getValue()){
                    simpleLeftRotate(node);
                }else {
                    rightLeftRotate(node);
                }
            }

        }
        node.setHeight(Math.max(getHeight(node.getLeftTree()),getHeight(node.getRightTree()))+1);
    }

    /**
     * 平衡树搜索方法
     * @param value
     * @return
     */
    public TreeNode search(int value){
        TreeNode node = root;
        while (node!=null){
            if(value==node.getValue()){
                break;
            }
            node = value<node.getValue()?node.getLeftTree():node.getRightTree();
        }
        return node;
    }

    /**
     * 平衡二叉树删除结点
     * @param node 递归根节点
     * @param value 待删除value
     * @return
     */
    public void delete(TreeNode node,int value){
        if(node==null){
            return;
        }else if(value<node.getValue()) {
            delete(node.getLeftTree(),value);
            if(getHeight(node.getLeftTree())-getHeight(node.getRightTree())==2){
                if(value<node.getLeftTree().getValue()){
                    simpleRightRotate(node);
                }else{
                    leftRightRotate(node);
                }
            }
        }else if(value>node.getValue()){
            delete(node.getRightTree(),value);
            if(getHeight(node.getLeftTree())-getHeight(node.getRightTree())==2){
                if(value>node.getLeftTree().getValue()){
                    simpleLeftRotate(node);
                }else{
                    rightLeftRotate(node);
                }
            }
        }else {
            //待删除节点为Leaf节点，直接删除
            if(node.getLeftTree()==null && node.getLeftTree() == null){
                node = null;
            }
            //左子树不为空，右子树为空
            else if(node.getLeftTree()!=null&&node.getRightTree()==null){
                node = node.getLeftTree();
            }
            //左子树为空，右子树不为空
            else if(node.getLeftTree()==null && node.getRightTree()!=null){
                node = node.getRightTree();
            }
            //左右子树都不为空
            else{
                TreeNode subTree = node.getRightTree();
                TreeNode subLeftTree = subTree.getLeftTree();
                if(subLeftTree==null){
                    subTree.setLeftTree(node.getLeftTree());
                    node = subTree;
                }else{
                    while (subLeftTree.getLeftTree()!=null){
                        subLeftTree = subLeftTree.getLeftTree();
                    }
                    node.setValue(subLeftTree.getValue());
                    delete(node.getRightTree(),subLeftTree.getValue());
                    node.setHeight(Math.max(getHeight(node.getLeftTree()),getHeight(node.getRightTree()))+1);
                }

            }
        }
        node.setHeight(Math.max(getHeight(node.getLeftTree()),getHeight(node.getRightTree()))+1);
    }


    /**
     * 获取树的高度
     * @param node
     * @return
     */
    private int getHeight(TreeNode node){
        int height = 0;
        if(node == null){
            height = -1;
        }else {
            height = node.getHeight();
        }
        return height;
    }

    /**
     * 插入位置为左子树的左孩子
     * 结点右旋
     * @param node
     * @return
     */
    private TreeNode simpleRightRotate(TreeNode node){
        TreeNode tmpRoot = null;
        if(node!=null){
            //结点右旋
            tmpRoot = node.getLeftTree();
            node.setLeftTree(tmpRoot.getRightTree());
            tmpRoot.setRightTree(node);
            node = tmpRoot;
            //重新计算树高
            node.setHeight(Math.max(node.getLeftTree().getHeight(),node.getRightTree().getHeight())+1);
            tmpRoot.setHeight(Math.max(tmpRoot.getLeftTree().getHeight(),tmpRoot.getRightTree().getHeight())+1);
        }
        return tmpRoot;
    }

    /**
     * 插入位置为右子树的右孩子
     * 结点左旋
     * @param node
     */
    public TreeNode simpleLeftRotate(TreeNode node){
        TreeNode tmpRoot = null;
        if(node!=null){
            //结点左旋
            tmpRoot = node.getRightTree();
            node.setLeftTree(tmpRoot.getLeftTree());
            tmpRoot.setLeftTree(node);
            node = tmpRoot;
            //重新计算树高度
            node.setHeight(Math.max(node.getLeftTree().getHeight(),node.getRightTree().getHeight())+1);
            tmpRoot.setHeight(Math.max(tmpRoot.getLeftTree().getHeight(),tmpRoot.getRightTree().getHeight())+1);
        }
        return tmpRoot;
    }

    /**
     * 插入位置为左子树的右孩子
     * 先进行左旋再进行右旋
     * @param node
     * @return
     */
    public TreeNode leftRightRotate(TreeNode node){
        TreeNode tmpRoot = null;
        if(node!=null){
            node.setLeftTree(simpleLeftRotate(node.getLeftTree()));
            tmpRoot = simpleRightRotate(node);
        }
        return tmpRoot;
    }

    /**
     * 插入位置为右子树的左孩子
     * 先进行右旋再进行左旋
     * @param node
     * @return
     */
    public TreeNode rightLeftRotate(TreeNode node){
        TreeNode tmpRoot = null;
        if(node!=null){
            node.setLeftTree(simpleRightRotate(node.getLeftTree()));
            tmpRoot = simpleLeftRotate(node);
        }
        return tmpRoot;
    }
}
